home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 January: Mac OS SDK / Dev.CD Jan 97 SDK2.toast / Development Kits (Disc 2) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc™ Source Code / Storage / Bento / CM / SymTbMgr.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-08-28  |  9.7 KB  |  262 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        SymTbMgr.c
  3.  
  4.     Contains:    Container Manager Binary Tree Symbol Table Routines
  5.  
  6.     Written by:    Ira L. Ruben
  7.  
  8.     Owned by:    Ed Lai
  9.  
  10.     Copyright:    © 1991-1994 by Apple Computer, Inc., all rights reserved.
  11.  
  12.     Change History (most recent first):
  13.  
  14.          <2>     8/26/94    EL        #1182319 The compare function in
  15.                                     lookUpSymbol now compare name to symbol
  16.                                     rather than symbol to symbol.
  17.          <1>      2/3/94    EL        first checked in
  18.  
  19.     To Do:
  20. */
  21.  
  22. /*---------------------------------------------------------------------------*
  23.  |                                                                           |
  24.  |                         <<<    SymTbMgr.c    >>>                          |
  25.  |                                                                           |
  26.  |            Container Manager Binary Tree Symbol Table Routines            |
  27.  |                                                                           |
  28.  |                               Ira L. Ruben                                |
  29.  |                                 11/18/91                                  |
  30.  |                                                                           |
  31.  |                  Copyright Apple Computer, Inc. 1991-1994                 |
  32.  |                           All rights reserved.                            |
  33.  |                                                                           |
  34.  *---------------------------------------------------------------------------*
  35.  
  36.  This file contains all the generic symbol table routines.  They are in the form of 
  37.  binary trees.  The three routines cmEnterSymbol(), cmLookupSymbol(), and cmForEachSymbol()
  38.  are the low level generic binary tree manipulators which higher level "glue" routines
  39.  use.
  40.  
  41.  All structs that are to be maintained as binary trees with this package must be of the
  42.  form:
  43.  
  44.                  struct {
  45.                     SymbolLinks theLinks;
  46.                     ...
  47.                 }...;
  48.                 
  49.  In other words, a field (any name will do) of type SymbolLinks MUST be the first field
  50.  of the structure.  The caller allocates all the struct symbol table entries.  This
  51.  package enters them into a symbol table based on a tree root pointer and maintains the
  52.  SymbolLinks.
  53.  
  54.  Being a generic package the links have to be at a know place in an otherwise arbitrary
  55.  struct.  Hence the position requirement.
  56. */
  57.  
  58.  
  59. #include <stddef.h>
  60.  
  61. #ifndef __CMTYPES__
  62. #include "CMTypes.h"
  63. #endif
  64. #ifndef __CM_API_TYPES__
  65. #include "CMAPITyp.h"
  66. #endif
  67. #ifndef __SYMMGR__
  68. #include "SymTbMgr.h"      
  69. #endif
  70. #ifndef __SESSIONDATA__
  71. #include "Session.h"          
  72. #endif
  73. #ifndef __HANDLERS__
  74. #include "Handlers.h"
  75. #endif
  76.                                                                     
  77.                                                                     CM_CFUNCTIONS
  78.  
  79. /* The following generates a segment directive for Mac only due to 32K Jump Table             */
  80. /* Limitations.  If you don't know what I'm talking about don't worry about it.  The        */
  81. /* default is not to generate the pragma.  Theoritically unknown pragmas in ANSI won't    */
  82. /* choke compilers that don't recognize them.  Besides why would they be looked at if        */
  83. /* it's being conditionally skipped over anyway?  I know, famous last words!                        */
  84.  
  85. #if CM_MPW
  86. #pragma segment SymbolTableMgr
  87. #endif
  88.  
  89.  
  90. /*---------------------------------------------------*
  91.  | cmEnterSymbol - enter a symbol into a binary tree |
  92.  *---------------------------------------------------*
  93.  
  94.  Enter the specified symbol into its own binary tree symbol table with the specified root.
  95.  The function returns a pointer to the entry if entered.  If the entry is already there,
  96.  the pointer to the dup entry is returned, dup is set to true, and no other action taken.
  97.  
  98.  It is assumed the space for the new symbol has already been allocated and its pointer
  99.  passed as the symbol here.
  100.  
  101.  The binary tree is searched utilizing a comparison function provided by the caller.
  102.  Compare is function that takes as arguments pointers to two symbols and returns -1 if the
  103.  first symbol is "less than" the second, 1 if the first symbol is "greater than" the 
  104.  second, and 0 if the tow symbols are equal.
  105. */
  106.  
  107. void *cmEnterSymbol(const void *symbol, void **root, Boolean *dup,
  108.                                         int (*compare)(const void *, const void *))
  109. {
  110.     int                          comparison;
  111.     SymbolLinksPtr p, prev;
  112.     Boolean              lLeft = false;
  113.     
  114.     /* Look up symbol in the tree...                                                                                                            */
  115.     
  116.     if ((p = *(SymbolLinksPtr *)root) == NULL)
  117.         prev = NULL;
  118.     else
  119.         do {
  120.             prev = p;
  121.             if ((comparison = (*compare)(p, symbol)) == 0) {
  122.                 *dup = true;                                                            /* if entry already in the table...        */
  123.                 return ((void *)p);                                                /* ...return ptr to it                                */
  124.             } else if (comparison < 0) {
  125.                 p = p->rLink; lLeft = false;
  126.             } else {
  127.                 p = p->lLink; lLeft = true;
  128.             }
  129.         } while (p);
  130.     
  131.     /* If we didn't find the symbol, enter it into the tree...                                                        */
  132.  
  133.     *dup = false;                                                                    /* we know it's not a dup here                    */
  134.  
  135.     ((SymbolLinksPtr)symbol)->lLink = ((SymbolLinksPtr)symbol)->rLink = NULL;    /* no links    */
  136.     
  137.     if (!prev)                                                                        /* hook new entry into tree                            */
  138.         *root = (void *)symbol;
  139.     else if (lLeft)
  140.         prev->lLink = (SymbolLinksPtr)symbol;
  141.     else
  142.         prev->rLink = (SymbolLinksPtr)symbol;
  143.     
  144.     return ((void *)symbol);                                            /* return new entry to caller                        */
  145. }
  146.  
  147.  
  148. /*-----------------------------------------------------------------------------*
  149.  | cmLookupSymbol - see if a symbol is already in its binary tree symbol table |
  150.  *-----------------------------------------------------------------------------*
  151.  
  152.  Look up the specified symbol in its binary tree symbol table which starts at the
  153.  specified root.  Return the pointer to it if found and NULL if not found.
  154.  
  155.  The binary tree is searched utilizing a comparison function provided by the caller. 
  156.  Compare is function that takes as arguments pointers to two symbols and returns -1 if the
  157.  first symbol is "less than" the second, 1 if the first symbol is "greater than" the 
  158.  second, and 0 if the tow symbols are equal.
  159.  
  160.  It used to be that both arguments of compare are symbols, but that requires the
  161.  temporary geneation of a symbol during lookup. So we change the comparision to
  162.  a symbol and a name to improve the performance.
  163. */
  164.  
  165. void *cmLookupSymbol(const CM_UCHAR *name, const void *root,
  166.                                           int (*compare)(const void *, const CM_UCHAR *))
  167. {
  168.     SymbolLinksPtr p;
  169.     int                       comparison;
  170.  
  171.     p = (SymbolLinksPtr)root;
  172.     while (p) {
  173.         if ((comparison = (*compare)(p, name)) == 0)
  174.             return ((void *)p);
  175.         else if (comparison < 0)
  176.             p = p->rLink;
  177.         else
  178.             p = p->lLink;
  179.     }
  180.     
  181.     return (NULL);
  182. }
  183.  
  184.  
  185. /*-------------------------------------------------*
  186.  | cmForEachSymbol - do some action on each symbol |
  187.  *-------------------------------------------------*
  188.  
  189.  Do (call) the specified action for each entry in a binary tree symbol table. This
  190.  routine recursively traverses the binary tree calling (*action)() on each entry visited.
  191.  The pointer to the entry is passed to the action routine along with a "refCon" which the
  192.  caller can use as a communication facility to convey additional info to the action
  193.  routine.
  194.  
  195.  The search in the binary tree starts at the specified symbol location.  Generally this
  196.  will be a root of a tree, but need not be.  Tree traversal is such that the symbols are
  197.  visited in "ascending" order, i.e., whatever order that was used by the compare
  198.  function passed to cmEnterSymbol().
  199. */
  200.  
  201. void cmForEachSymbol(const void *symbol, CMRefCon refCon,
  202.                                         void (*action)(void *symbol, CMRefCon refCon))
  203. {
  204.     void *lLink, *rLink;
  205.     
  206.     if (symbol) {                                                                /* if we got a symbol...                                    */
  207.         lLink = ((SymbolLinksPtr)symbol)->lLink;    /* ...hold on to links in case action does*/
  208.         rLink = ((SymbolLinksPtr)symbol)->rLink;    /*    something "radical" with the entries*/
  209.     
  210.         cmForEachSymbol(lLink, refCon, action);        /* ...follow the left link down                        */
  211.         (*action)((void *)symbol, (void *)refCon);/* ...perform action at a leaf                        */
  212.         cmForEachSymbol(rLink, refCon, action);        /* ...do same for the right links                    */
  213.     }
  214. }
  215.  
  216.  
  217. /*---------------------------------------------------------------------------------------*
  218.  | freeSymbols - free all symbols in a binary tree symbol tbl (guts of cmFreeAllSymbols) |
  219.  *---------------------------------------------------------------------------------------*
  220.  
  221.  This is used only by cmFreeAllSymbols() to walk the symbol table binary tree to free all
  222.  the symbols in it.  It is functionally equivalent to cmForEachSymbol() above. Indeed we
  223.  could have used (and once upon a time, did) cmForEachSymbol() if it we not for the refCon
  224.  usage!
  225. */
  226.  
  227. static void CM_NEAR freeSymbols(const void *symbol, SessionGlobalDataPtr sessionData)
  228. {
  229.     void *lLink, *rLink;
  230.     
  231.     if (symbol) {                                                                /* if we got a symbol...                                    */
  232.         lLink = ((SymbolLinksPtr)symbol)->lLink;    /* get the two links...                                        */
  233.         rLink = ((SymbolLinksPtr)symbol)->rLink;
  234.         
  235.         freeSymbols(lLink, sessionData);                    /* ...follow the left link down                        */
  236.         SessionFree(symbol);                                            /* ...free a symbol                                                */
  237.         freeSymbols(rLink, sessionData);                    /* ...do same for the right links                    */
  238.     }
  239. }
  240.  
  241.  
  242. /*-------------------------------------------------------------------------*
  243.  | cmFreeAllSymbols - remove all the symbols in a binary tree symbol table |
  244.  *-------------------------------------------------------------------------*
  245.  
  246.  This routine takes a root of a binary tree symbol table and deletes ALL the entries in
  247.  the table.  The root pointer is returned as NULL.
  248.  
  249.  Note, that SymbolTableMgr routines are low level routines used in a number of contexts.
  250.  Here we need to uutilize the container memory deallocator handler.  Because we don't
  251.  know the context, which may be global, the session global data pointer is passed and we
  252.  access the handler through that.
  253. */
  254.  
  255. void cmFreeAllSymbols(void **root, SessionGlobalDataPtr sessionData)
  256. {
  257.     freeSymbols(*root, sessionData);
  258.     *root = NULL;
  259. }
  260.                                                           
  261.                                                             CM_END_CFUNCTIONS
  262.